package myself.a010BinaryTreeRecursion;

/**
 * @author 叶之越
 * Description
 * Date 2021/1/27
 * Time 22:26
 * Mail 739153436@qq.com
 */
public class IsFull {

    // 判断满二叉树
    public static boolean isFull2(Node head) {
        if (head == null) {
            return true;
        }
        Info all = process(head);
        return (1 << all.height) - 1 == all.nodes;
    }

    public static Info process(Node head) {
        if (head == null) {
            return new Info(0, 0);
        }
        Info left = process(head.left);
        Info right = process(head.right);

        return new Info(Math.max(left.height, right.height) + 1, left.nodes + right.nodes + 1);
    }

    public static class Info {
        public int height;
        public int nodes;

        public Info(int height, int nodes) {
            this.height = height;
            this.nodes = nodes;
        }
    }

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }
}
